// 自定义的类作为unsorted hash based容器的key值需要写hash函数 复杂度是log(1)
// 自定义的类作为sorted hash based容器的key值需要写比较函数 复杂度是log(n)

// 哈希函数在C++类设计中的作用
// 哈希函数在C++类设计中扮演着重要角色，特别是当您希望您的自定义类能够与标准库
// 的关联容器（如std::unordered_map和std::unordered_set）一起使用时。

// 什么是哈希函数？
// 哈希函数是一种将任意大小的数据映射到固定大小值（通常是整数）的函数。
// 这个固定大小的值被称为哈希值或哈希码。
// 在C++中，std::hash是一个函数对象（functor），为基本类型和一些标准库类型提供了哈希实现。

// 为什么需要为自定义类型提供哈希函数？
// 1. 使用基于哈希的容器
// C++标准库提供了两类主要的关联容器：
// 有序容器：std::map, std::set, std::multimap, std::multiset
// 这些容器基于比较操作（通常是operator<）排序元素
// 无序容器：std::unordered_map, std::unordered_set, std::unordered_multimap, std::unordered_multiset
// 这些容器基于哈希表实现，需要一个哈希函数来计算元素的存储位置

// 如果您想将自定义类型作为无序容器的键，就需要提供一个哈希函数。

// 2. 实际例子：使用Customer作为键
// 假设您有一个Customer类，并想创建一个从Customer到其订单信息的映射：
class Customer
{
public:
    Customer(std::string name, int id) : name(name), id(id) {}

    std::string getName() const { return name; }
    int getId() const { return id; }

    // 定义相等比较
    bool operator==(const Customer &other) const
    {
        return id == other.id && name == other.name;
    }

private:
    std::string name;
    int id;
};

// 没有自定义哈希函数时，以下代码会编译失败
std::unordered_map<Customer, OrderInfo> customerOrders; // 错误!
// 上面的代码会失败，因为std::unordered_map需要一个哈希函数来处理Customer类型的键，但标准库不知道如何哈希您的自定义类型。
// 在std命名空间中特化hash模板

/**
 * @details
 * std::hash是定义在std命名空间中的模板
 * 要特化一个模板，必须在其原始命名空间中进行特化
 * 这是C++的规则：模板特化必须出现在与原始模板相同的命名空间中
 * 注意：通常不建议在std命名空间中添加新内容，但模板特化是一个例外，C++标准明确允许这种做法。
 *
 */
namespace std
{
    template <> // template<>表示"这是一个完全特化的模板"
    struct hash<Customer>
    {
        // 这定义了std::hash模板针对Customer类型的特化
        // 它创建了一个函数对象（functor），可以计算Customer对象的哈希值
        // 这个特化告诉C++ 标准库如何为Customer类型生成哈希值
        size_t operator()(const Customer &c) const
        {
            // 组合现有的哈希函数
            return hash<string>()(c.getName()) ^
                   (hash<int>()(c.getId()) << 1);
        }
    };
}

// 现在可以使用Customer作为键了
std::unordered_map<Customer, OrderInfo> customerOrders; // 正确!

// 哈希函数与比较函数的关系
// 在使用哈希容器时，需要两个关键组件：

// 哈希函数：确定元素应该存储在哪个"桶"中
// 相等比较：确定两个元素是否相同（通常是operator==）
// 这两个组件必须保持一致：如果两个对象通过operator==被认为是相等的，它们必须产生相同的哈希值。反之则不必成立（不同的对象可以有相同的哈希值，这称为"哈希冲突"）。